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)

0
votes
1answer
41 views

homework - combinatorics number of possibilties

We have 28 balls, 13 red and 15 blue. What is the number of possibilities to split them to 3 cells when: 1) The number of balls in the first cell is exactly 12 AND 2) The number of red balls is not ...
0
votes
1answer
51 views

A Proof Question

Prove : $$\sum_{k=1}^nkp(n,k)=n!\;,$$ where $p(n,k)$ is the number of permutations of $\{1,2,\ldots, n\}$ which have exactly $k$ fixed points. I was using $$p(n,k) = \frac{n!}{(n-p)!}$$ and ...
0
votes
0answers
44 views

The formula for a perhaps basic identity

We know the expansion of the following product $\prod_{k=1}^n(1+x+y_k)$ can be expressed by the formula $\sum_{k=0}^n(1+x)^{n-k}s_k(y_1, \ldots, y_n),$ where the $s_k$'s are the elementary ...
4
votes
3answers
48k views

how many ways can the letters in ARRANGEMENT can be arranged [closed]

In how many different ways can the letters in the word ARRANGEMENT be arranged?
0
votes
0answers
23 views

A variant of submodularity?

See the definition of submodulation functions: $$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B) $$ Suppose I make this definition a little stronger: $$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B) + A ...
9
votes
1answer
136 views

Collection of subsets with adding one element property

Let $\mathcal{F}$ be a collection of subsets of $\{1,2,\ldots,n\}$ such that for any set $A\in\mathcal{F}$, there exists $B\not\in \mathcal{F}$ such that $A\subset B\subseteq\{1,2,\ldots,n\}$ and ...
0
votes
4answers
39 views

the summation of sequences $n{\alpha}^n$?

what is the the summation $S_n = \sum\limits_{n = 1}^\infty{b_n} $ with $b_n = n{\alpha}^n$? Here $0 \le \alpha < 1$. any closed form solution? I know maybe we should build a geometric sequence ...
1
vote
3answers
25 views

Choosing three pairs out of eight items

3 students each choose two problems from a list of eight problems. How many ways can this be done? The answer in the text book gives 8!/(2! 2! 2! 2!), but don't we also have to multiply by the ...
3
votes
0answers
43 views

Combinatorial problem that a friend asked with some interesting stipulations

If there are 6 candidates and each is allotted one vote, but cannot vote for him or herself, what is the likelihood of each candidate taking a majority vote? A multi-way tie? If given a specified ...
3
votes
3answers
108 views

Card Game Probability 13 Card Hand

Me and my friends play a four person poker style card game. Each person is dealt 13 cards, and it is a standard trump card game. Now, as the standard, a five card flush beats a five card straight, but ...
2
votes
4answers
96 views

Finding all possible combinations in a specific case

Lets say I have a set such as (1, 1, 1, 1) where each number can be from 1 to 100. All possible combinations will be (1, 1, 1, 1), (1, 1, 1, 2), ... , (1, 1, 1, 100), ... (100, 100, 100, 100). Order ...
0
votes
0answers
74 views

How to count number of cyclic permutations

I have a set $\{1, 2, 3, 4, 5, 6\}$ and I want to get number of cyclic permutations like $\{1, 2, 4, 5, 6, 3\}$. But the next numbers in this cycle must be not greater than three. So next to $1$ can ...
1
vote
1answer
47 views

What is the chromatic index of a complete graph with its edges doubled?

If $G$ is a graph, let $G'$ denote the graph obtained by doubling each edge of $G$. How can I show that $\chi'(G')=2\chi'(G)$? I am considering the two cases when $G$ is a complete graph $K_n$ with ...
0
votes
1answer
51 views

Probability questions based on mutual exclusion

I'm appearing for an exam for which I'm giving mock tests, however I came across this particular question that I'm unable to solve, it says: A certain experiment has three possible outcomes. The ...
1
vote
1answer
35 views

“Stars and Bars” method when all variables are multiple of same number

Find the number of non negative integral solutions of the equation $x + y + z + u = 100$, where $x, y, z$ and $u$ are multiple of $5.$ My approach using stars and bars: Since all are multiples of ...
0
votes
1answer
25 views

Questions about k elements subset of an n elements set.

I need to prove by induction that the number of 2-elements subset of an n elements set is $\frac{n(n-1)}{2}$ I am stuck on where I should start from and how should I solve this. I am guessing that ...
0
votes
1answer
66 views

Combinatorial prime puzzle

Is it true that no prime larger than $241$ can be made by either acting or subtracting $2$ coprime numbers made up out of the prime factors $2,3,$ and $5?$ Update Above example is clearly wrong, as ...
0
votes
0answers
43 views

Does there exist a covering of a square?

Consider a square of length $ S \in \mathbb{N} $ and a given set $ M $ of $ t \in \mathbb{N} $ smaller squares of lengths $ s_1,\ldots,s_t \in \mathbb{N} $. Are there any conditions, so that I can ...
1
vote
0answers
37 views

For fun, how many paths are there in a flow matrix?

I just got done doing the whole flow-matrix percolation exercise in programming. That is a situation where you have, for simplicity, an $n\times n$ grid of 0s and 1s. 0s represent blocked sites and ...
2
votes
4answers
170 views

Problem on selecting group of card from a well shuffled pack of card

I have a problem I'm working on: The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 card to guarantee that three cards are from some same suit is which amount? I got ...
6
votes
5answers
759 views

Even Number cards?

There are $15$ cards on a table, marked with an integer $1$ from to $15$ . How many ways can I take cards such that the sum of the numbers on the cards is even? Please help me?
4
votes
1answer
153 views

The no. of ways dividing a polygon with $n+1$ sides into triangular regions…

Please if any one can help me explaining this concept, I can't proceed further due to this.... Let $h(n)$ denote the no. of ways dividing a convex polygon region with $(n+1)$ sides into ...
1
vote
2answers
56 views

How many distinct solutions are there?

Suppose you put the numbers $1,2,\cdots ,10$ in each of the boxes below such that every connected row and column sum to the same number. How many distinct solutions are there? (By distinct we mean ...
2
votes
3answers
46 views

Algebra question / conversion of ranges

Greets All Forgive me if I'm using the wrong terms but I'm trying to sync up two number ranges together. Example: I have two x axis (ranges) I would like to equate with each other ...
3
votes
1answer
105 views

Kraft-McMillan inequality

Let $F$ be a finite collection of binary string of finite lengths and assume that no two distinct concatenations of two finite sequences of codewords result in the same binary sequence. Let $N_i$ ...
0
votes
1answer
56 views

Compute the number of subsets of (1,2,3,…20) with four elements such that no two elements are consecutive

Compute the number of subsets of (1,2,3,...20) with four elements such that no two elements are consecutive. Please explain explicitly! Thank you very much!!
0
votes
0answers
44 views

Variation of Bin-packing with classes of bins and objects

I'm working on a problem that is a variation of bin-packing, but a bit more general form with extra constraints. The problem definition is as follows- We have objects of varying sizes, which can be ...
1
vote
2answers
188 views

Pigeonhole Principle Problem with a standard deck of cards

If I have a standard deck of cards, how man cards must I draw to ensure that I get three cards of the same kind. How many cards must I draw ensure that I get 5 cards of the same suit. I am new to ...
0
votes
1answer
37 views

Parking lot, combinatorics

Consider the following situation. There are 8 free spots in the parking lot. The places get occupied by 5 women and 3 men. How many arrangements are possible if 2 women would occupy the first and the ...
0
votes
2answers
24 views

Choosing from movies, combinatorics

There are, 11 action movies, 9 romantic movies, and 5 thrillers. How many possibities are there to arrange this movies such that all 9 romantic movies stay together? This should be the solution from ...
0
votes
1answer
45 views

Is there a mathematical way to know exactly how many substrings , prefixes , suffixes does a string have. for example w=“abbcc”

My trials were for prefixes and suffixes including the empty string for "abbcc" were equal to the (length_of_the_string + 1) but I couldn't figure out a way for calculating the number of substrings .
0
votes
1answer
35 views

Enumerate all the combinations given a constraint

Assume there are $N$ non-negative integer numbers: $a_1,\ldots,a_N$. How can one enumerate all the possible combinations of $(a_1,\ldots,a_N)$ which satisfy the following inequality: $\sum _{n=1}^N ...
0
votes
1answer
45 views

Permutation of $n$ women and $m$ men, in a line, where the women dont get along with each other

So the $n$ women can't sit next to each other. So in a straight line how many ways can they be seated? I know this problem is partitioning distinct balls in $n+1$ partitions, out of which $n-1$ of ...
0
votes
0answers
25 views

Least graph containing every connected graph with $m$ nodes as an induced subgraph

What is the smallest graph that contains every connected graph with $m$ nodes as an induced subgraph ? If the graph has $n$ nodes, there are $\binom{n}{m}$ (not necessariliy distinct) subgraphs with ...
0
votes
1answer
40 views

how to calculate these intersections without having to count all combinations

We have the following sets: $X= {(a,b,c,d) ∈S: b< c < d},$ $Y= {(a,b,c,d) ∈S: a< c < d},$ $Z= {(a,b,c,d) ∈S: a< b < d},$ $F= {(a,b,c,d) ∈S: a< b < c},$ Where each of ...
1
vote
1answer
54 views

How many ways to make a $3$ digits even number

How many ways to make a $3$ digits even number with only $2,3,5,6,7$ . And no repeated use of digit. I think I did something like for the first digit you have $5$ choices, for second digit $4$ ...
1
vote
2answers
64 views

Why is the arrangement of $n$ things round a circular table is $(n - 1)!$ & not $n!$ ?

Suppose there are $n$ seats round a table . We have to find the number of circular permutations of $n$ different men taken all at a time when clockwise & anti-clockwise orders are different. ...
2
votes
3answers
53 views

Probability of $2$ boys in a family.

In a family there are 3 children with minimum $1$ boy.What is the probability there are exactly $2$ boys in the family? I think I have to use combinatorics to solve this problem. I have solved some ...
3
votes
1answer
52 views

Find the number of possible 4x4 matrices such that :

Find the number of possible 4x4 matrices such that : 1) each row has two 0's and two 1's 2) each column has two 0's and two 1's example : $$\large \begin{pmatrix} ...
2
votes
1answer
67 views

Probability of a drawing a specific suit and a specific color

After drawing 5 cards from a standard 52 card deck, what is the probability that the hand will contain: 1 diamond 1 spade Any other red card (diamond or heart) My first approach was to use a ...
3
votes
2answers
48 views

Prove that sum $\sum_{k=1}^n {(-1)^k {{n-1} \choose {k-1}} (2n-k-1) 2^k}$ is zero

I try to prove that $\sum_{k=1}^n {(-1)^k {{n-1} \choose {k-1}} (2n-k-1) 2^k}=0.$ I calculated in Maple for n=1..100. $\sum_{k=1}^n {(-1)^k {{n-1} \choose {k-1}} (2n-k-1) 2^k}=-2 \sum_{k=0}^{n-1} ...
3
votes
4answers
182 views

proving an invloved combinatorial identity

How to prove following Identity? $$\sum_{k=0}^n (-1)^k {n-k \choose k} m^k (m+1)^{n-2k} = \frac {m^{n+1}-1}{m-1}, m \ge 2$$ This seems very hard to me. Any idea about how to prove it combinatorialy? ...
1
vote
1answer
45 views

A Question about Shuffling a Deck of Cards

Currently I am following Sheldon Ross' A first course in probability. And I got stuck in this question: Consider the following technique for shuffling a deck of $n$ cards: For any initial ordering of ...
0
votes
2answers
54 views

Is there a simple graph with an odd number of automorphisms (except $1$ and $3$)?

The simple graphs upto $11$ vertices do not have $5,7,9,...$ automorphisms, in other words, the only odd numbers appearing are $1$ and $3$. Is this true for all graphs ? Formulated as an ...
2
votes
2answers
76 views

Binomial theorem - a special case. Calculate sums.

I have just started my first course in discrete math and have some reflections. If I want to calculate the sum ${n \choose 0}+{n \choose 1}x+{n \choose 2}x^2+...+{n \choose n-1}x^{n-1}+{n \choose ...
4
votes
2answers
59 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( ...
1
vote
3answers
148 views

Problem with concepts of circular permutation.

I am having problem in understanding this concept: Circular permutation : The definition in my book goes like that ' Arrangements of things in a circle or a ring are called circular ...
1
vote
2answers
71 views

Can we express the following ordinary generating function?

I wish to express the following power series $$ \sum_{k \ge 0} \binom{n-k}{m} x^k$$ where $n,m$ are positive integer such that $0< m \le n$
4
votes
1answer
89 views

Partition in graph connecting itself and other half

Let $G=(V,E)$ be a graph with $n$ vertices and minimum degree $\delta>10$. Prove that there is a partition of $V$ into two disjoint subsets $A$ and $B$ so that $|A|\leq ...
7
votes
6answers
745 views

Different approaches to N balls and m boxes problem

Suppose that you have N indistinguishable balls that are to be distributed in m boxes (the boxes are numbered from 1 to m). What is the probability of the i-th box being empty (where the i-th box is ...