For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

4
votes
2answers
72 views

Nested Sum Encountered in Maclaurin Expansion of $e^{-x^2}$

In the course of working out the Maclaurin expansions of $e^{-x^2}$ and $cos(x^2)$, I ran into the following nested sum: $$ \underbrace{ \sum_{a=0}^1 \left( a \sum_{b=0}^{a+1} b \left( \sum_{c=0}^{b+...
2
votes
2answers
253 views

How to find the optimal mapping between two sets?

Given two sets $A$ and $B$, both of $n$ points $p \in \mathbb{R}^3$. I want to find a bijective function $f:A \rightarrow B$ so that the cost $C$ is minimal. It's defined as the sum of all pair's ...
1
vote
2answers
65 views

Discrete Mathematics - In how many ways can $A$ and $B$ exchange their books?

$A$ has $5$ different books and $B$ has $3$ different books. How many ways are there in which they can exchange their books so that each keeps his individual number of books unchanged? I got the ...
0
votes
3answers
91 views

List all the permutations for the letters $a,c,t$

I know a permutation is $p(n,r)=\dfrac{n!}{(n-r)!}$ but I am confused how to go about solving this problem. Help please?
2
votes
3answers
166 views

Another question about ratios of Pochhammer symbols

My question is similar to this question. Can $$\frac{(11/6)_n (7/6)_n (3/2)_n}{(3)_n}$$ be expressed 'nicely' in terms of factorials just like $(1/6)_n (1/2)_n (5/6)_n$ in the aforementioned question? ...
3
votes
3answers
165 views

Evaluate the sum

I need to evaluate the following sum, which depends on $n \in \mathbb N$ (call it $S(n)$ if you will) $$ \sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$$ where $f$ defined over $\mathbb N$ is ...
2
votes
2answers
58 views

Combinations: People want a beer, there are certain kinds of beer, but limited numbers of each kind

Four people go to a pub and each wants to drink a pint of either the lager, ale, or porter. However, there are only 2 pints of lager, 1 ale, and 1 porter available to drink. How many combinations of ...
1
vote
2answers
101 views

Number of subsets of a set $S$ of n elements , is $2^n$ [duplicate]

I know that Number of subsets of a set $S$ of size n , is given by the binomial sum $\sum_{k=0} ^n \binom{n}{k}=2^n$ , n=1,2,3,.. elements how we could conclude of prove this formula ? ...
14
votes
2answers
621 views

Identity with Catalan numbers

How would you prove the following identity $$\sum_{1\ \leq\ j\ <\ j'\ \leq\ n}\ \prod_{k\ \neq\ j,\,j'}^{n} {\left(\, j + j'\,\right)^{2} \over \left(\, j - k\,\right)\left(\, j' - k\,\right)} =...
0
votes
4answers
267 views

a 2-regular graph is cyclic or not?

We know the common result : - If every vertex of a graph G has degree at least2, then G contains a cycle. Can I conclude that 2-regular graphs are cycles where degree is exactly two of every vertex? I ...
0
votes
1answer
67 views

Number of ways two matrices can be multiplied?

Given the dimensions of two matrices what are the different ways they can be multiplied? Example $A[2][2]$ and $B[2][2]$ then answer is $2$. Let the dimensions of first matrix be $n \times m$ and ...
6
votes
1answer
341 views

Counting graph isomorphisms and entropy

Question: If all graphs on $n$ vertices are given equal probability, what does the induced probability distribution on the graph isomorphism classes look like? Are there any patterns that emerge as ...
2
votes
1answer
80 views

Set of numbers that add up 1 to n

I am currently trying to solve the following problem: Given a number $n \in \mathbb{N}$, find the size of a set $S$ of positive numbers $s_1, \ldots, s_k\in \mathbb{N}$, such that $\sum_{i=1}^kS_i ...
0
votes
1answer
45 views

Probabilistic method in coloring of graph

I was reading Noga Alon's Probabilistic Methods and came across this question which I am unable to prove. There is a two-coloring of $K_n$ where $K_n$ is a complete graph of $n$ vertices with at most ...
0
votes
3answers
47 views

Combinatorics Ordered Pair of embeded Subsets

Let X be the set {1,2, .... n}. Count the number of ordered pairs (A, B) where A and B are subsets of X and A is a subset of B. I'm just starting to learn how combinatorics works and I have no clue ...
2
votes
1answer
92 views

Numbers which are writable as a sum of permutation pairs

We say that $N$ is writable as a sum of permutation pair $\{a,b\}$ if $a+b=N$, $a\neq b$ and $a$ and $b$ are permutations of each other (e.g. $321 = 156 + 165 = 147 + 174 = ... $). Looking at 3-digit ...
0
votes
2answers
68 views

Does this combination problem count the repeats

To use a certain cash machine, you need a Personal Identification Code (PIC). If each PIC consists of two letters followed by one of the digits from 1 to 9 (such as AQ7 or BB3) or one letter followed ...
2
votes
1answer
1k views

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if $1$ and $n$ also count as consecutive?

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if 1 and n also count as consecutive? It looks that the number of such subsets obeys the (...
1
vote
1answer
67 views

Dilworths Theorem proof doubt

This is the proof I am talking about http://www.math.cmu.edu/~af1p/Teaching/Combinatorics/F03/Class14.pdf When you take a maximal chain C in P and then obtain antichains in P\C, if the size of the ...
5
votes
3answers
533 views

Generating Functions and Linear Diophantine Inequalities

The following exercise is from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick, page 46. A $k$-composition of $n$ is an ordered $k$-tuple of non-negative integers whose sum is $n$. ...
0
votes
2answers
2k views

Conditional probability: At least 3 kings given there are at least 2 kings in the hand of 13.

My first "conditional probability" problem. Sorry for all the questions. My instructor doesn't make sense to the class. A hand of 13 cards is to be dealt at random and without any replacement from an ...
1
vote
3answers
494 views

5-letter strings using the letters in the word “EVERGREEN”

From the word EVERGREEN, 5 letters are chosen at random and arranged into a string of letters. What is the probability that this string is palindromic?
0
votes
2answers
234 views

probability, 2 chips drawn have either same number or color

I've viewed similar problems to this, but I'm not understanding the logic to the question and answers behind them. There are 5 red chips (each numbered 1, 2, 3, 4, & 5), and 3 blue chips (each ...
1
vote
1answer
540 views

How to calculate the cardinality of the intersection of three sets?

I have a universe (or total number of people polled who are distributed amongst these sets) of $151$ persons. These sets correspond to which TV shows they watch (i.e., each set represents one TV show)...
1
vote
3answers
286 views

Probability You Choose at least one chip of every color

There are 16 chips: 6 red, 7 white, and 3 blue. 4 chips are selected randomly and are not replaced once selected. What is the probability that at least one chip of every color is selected? I'm not ...
2
votes
3answers
134 views

Proving that $(xy)!/y!^x$ is an integer

I'm learning about factorials and combinatorics in class, and this problem came up, but I don't know how to solve it. The teacher said that it would be an integer, but how can I show this? $$ \frac{\...
1
vote
1answer
73 views

Ternary Golay codes and correction probability

We define the probability of a given linear binary code C [n,k] as: $$P_{corr}(C)=\sum_{i=0}^n\alpha_i(p)^i(1-p)^{n-i}$$ Where $\alpha_i$ is the number of coset leaders of weight $i$. I am asked to ...
2
votes
4answers
76 views

Exotic proofs of $\sum_{j=0}^{n-1}\binom{p+j}{p}=\binom{p+n}{p+1}$

Let $p,n$ be positive integers. The following identity $\displaystyle \sum_{j=0}^{n-1}\binom{p+j}{p}=\binom{p+n}{p+1}$ may be proved by induction or by successive uses of Pascal's rule (both ...
7
votes
2answers
290 views

Does anyone recognise this recursion sastisfied by the Bell numbers?

I derived a recursion $$B_n=\frac{1}{n}B_0+\frac{1}{n}\sum_{k=1}^{n-1}\left[\binom{n}{k}-(-1)^{n-k}\binom{n}{k-1}\right]B_k\tag{$*$}$$ which I know should be satisfied by the moments of the unit ...
1
vote
1answer
99 views

Extended Golay Code - Vectors of Odd Weight

In V(24,2) every vector of odd weight is at distance at most 3 from some code-word in $G_{24}$, the extended binary golay code. This seems to be a known result appearing in many texts and papers, ...
3
votes
1answer
56 views

Symmetries on sets of strings

My question is a reference request about symmetries on sets of strings. I'm not a mathematician, so the terminology I use below is probably very non-standard. My apologies. Terminology. Let $[n] = \{...
1
vote
4answers
43 views

Find $n(A \cap B)$

Question: In group of people, 60% like coffee and 70% like tea. How many people like both of them.? My Effort: We have to find how many people like both the items that means we have to find $n(A \...
3
votes
1answer
102 views

Decomposing the Complete Graph into Forests

Which spanning forests can we partition the complete graph $K_n$ into? I am primarily interested in partitions into one fixed isomorphism class of forest. I'm also assuming whatever divisibility ...
0
votes
2answers
55 views

Counting sequences of increasing numbers that may be equal

What is the number of sequences $(a_1,a_2,\dots ,a_k)$ of length $k$ such that $a_1,a_2,\dots,a_k$ are in the set $\{1,2,\dots,n\}$ and $a_1\le a_2 \le \dots \le a_k$? I have worked on this problem ...
0
votes
2answers
1k views

Converting seconds into days, hours, minutes, and seconds

I'm working on an assignment for a computer science class, but am having a little trouble. Here is the problem: If we use a modem to transfer files, how long will it take to transfer 1,288,490,188,800 ...
1
vote
1answer
65 views

Let $L$ and $L'$ be lattices. Prove that $L \times L'$ is also a lattice.

Can someone please verify my proof or offer suggestions for improvement? Some preliminaries: Let $A$ and $B$ be two posets. $A \times B$ is the poset on the cartesian product of $A$ and $B$ such ...
1
vote
0answers
57 views

Simple König theorem

I have to prove the "simple" König theorem, without using the marriage theorem: Let $S$ be a set of size $mn$. Suppose that $S$ is partitioned into $m$ subsets, all having size $n$, in two ways: $A_1,...
1
vote
0answers
38 views

Prove that $P$ is a lattice (details inside)

Can someone please verify my proof or offer suggestions for improvement? There may be answers to the same questions elsewhere, but I need help with my proof in particular. Show that if $P$ is a ...
1
vote
2answers
46 views

Permutations on 5 letters

I was doing a riddle which said "five points are randomly distributed on the circumference of a circle. From any of these points, a continuous line may be drawn that connects the other points on the ...
1
vote
1answer
51 views

Let $P$ be a finite poset. Show that the number of order ideals equals the number of antichains.

Can someone please verify my proof or offer suggestions for improvement? I am aware that there are similar questions posted elsewhere, but I need help with my proof in particular. Some preliminaries: ...
2
votes
3answers
72 views

Probability of caugh at least 1 of one type of fish

In the lake we have got 3 types of fish: k - number of roach 2k - number of crucian 4k - number of perch Mr Smith caught 7 fish. What is a probability that Mr Smith caught at least 1 roach. My ...
6
votes
1answer
252 views

A method of making a graph bipartite

If we take a graph $G$, and sequentially delete the edge which belongs to the most odd cycles until we have a bipartite graph, will at least half the edges remain when the graph is bipartite? ...
2
votes
0answers
38 views

Let $P, Q, R$ be finite posets. Prove that $P^{Q+R} \cong P^Q \times P^R$.

Can someone please verify my proof and offer suggestions for improvement? I feel that my proof might have been a little hand-waving in showing that $\varphi$ is a bijection, and I feel that it is not ...
-1
votes
1answer
81 views

Number of ways to empty three boxes in a given number of steps, while taking at most one ball from each box at every step

Given a set of three boxes, each of which contains number of balls (say $x,y,z$ respectively), we have to empty the all the three boxes in exactly $N$ steps. At each step we have to pick at least $1$...
1
vote
3answers
49 views

Combinations of winning scholarships

If six students are eligible for two scholarships worth 1k each, how many different combinations of 2 students winning the 2 scholarships are possible? My attempt 6 nCr 2. How am I wrong?
1
vote
1answer
87 views

Binomial Congruence (mod 5) Identity

I've got a (hard?) Putnam-style problem that I've been given to look at . . . I've never worked any problem even vaguely like this, but my director thinks I should be able to do it. I doubt it (100% ...
4
votes
1answer
87 views

Let $S$ denote the set of all functions $f :\{0,1\}^4 \rightarrow \{0,1\}$. What is the number of functions from the set $S$ to the set $\{0,1\}$?

They say the answer is $2^{2^{16}}$ but I think the answer is $3^{3^{16}}$ because they have not specified the functions to be total. Am I correct? PS: I am a newbie so please don't be too harsh if ...
4
votes
3answers
118 views

Counting partition of set that $i$ and $i+1$ are not in one part

I have to count the number of partitions of the set $\{1,\ldots,n\}$ under the constraint that for each $i$, the elements $i$ and $i+1$ are in different parts. The my idea is: We have two situation ...
3
votes
0answers
56 views

Combinatorial interpretation of an equality

In a recent project, I came up with the following equality which turned out to be extremely useful for counting conjugacy classes in certain division algebras (I won't go into the details here, it's ...
1
vote
3answers
86 views

If I have 12 books and 12 book spaces, how many ways can I arrange these books? Not all spaces have to be filled. All the books are the same.

If I have 12 books and 12 book spaces, how many ways can I arrange these books? Not all spaces have to be filled. All the books are the same. In other words, putting a book in space 1 and a book in ...